/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 26727
 * Date: 2024-08-29
 * Time: 10:50
 */

import java.util.PriorityQueue;

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
//解法一：利用小根堆
class Solution4 {
    public ListNode mergeKLists(ListNode[] lists) {
        // 1.创建小根堆
        PriorityQueue<ListNode> heap = new PriorityQueue<>((v1, v2) -> v1.val-v2.val);

        // 2.把所有头结点放进小根堆
        for(ListNode head : lists) {
            if(head != null) {
                heap.offer(head);
            }
        }

        // 3.合并链表
        ListNode ret = new ListNode(0);
        ListNode prev = ret;

        while(!heap.isEmpty()) {
            ListNode t = heap.poll();
            prev.next = t;
            prev = t;
            if(t.next != null) {
                heap.offer(t.next);
            }
        }
        return ret.next;
    }
}

//解法二：递归
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
//class Solution {
//    public ListNode mergeKLists(ListNode[] lists) {
//        return merge(lists,0,lists.length-1);
//    }
//
//    public ListNode merge(ListNode[] lists,int left,int right) {
//        // 边界处理
//        if(left > right) {
//            return null;
//        }
//        if(left == right) {
//            return lists[left];
//        }
//
//        // 1.平分数组
//        int mid = (left+right)/2;
//        // [left,mid] [mid+1,right]
//        // 2.递归处理
//        ListNode l1 = merge(lists,left,mid);
//        ListNode l2 = merge(lists,mid+1,right);
//
//        // 3.合并两个有序链表
//        return mergeTwoList(l1,l2);
//    }
//
//    public ListNode mergeTwoList(ListNode l1,ListNode l2) {
//        if(l1 == null) return l2;
//        if(l2 == null) return l1;
//
//        ListNode head = new ListNode(0);
//        ListNode ret = head;
//
//        while(l1 != null && l2 != null) {
//            if(l1.val <= l2.val) {
//                ret.next = l1;
//                ret = l1;
//                l1 = l1.next;
//            }else {
//                ret.next = l2;
//                ret = l2;
//                l2 = l2.next;
//            }
//        }
//
//        if(l1 != null) {
//            ret.next = l1;
//        }
//        if(l2 != null) {
//            ret.next = l2;
//        }
//        return head.next;
//    }
//}

